/*
https://leetcode.cn/problems/trapping-rain-water/submissions/581568936/
*/
class Solution {
public:
    int trap(vector<int>& nums) {
        int ans=0;
        int n = nums.size();
        stack<int> st;
        for (int i =0; i <n  ; ++i) {
            int t=nums[i];
            while (!st.empty() && t >= nums[st.top()]) {
                int last_h=nums[st.top()];
                st.pop();
                if(st.empty()){
                break;
                }
                int left=st.top();
                int dh=min(nums[left],nums[i])-last_h;
                ans+=dh*(i-left-1);
            }
            
            st.push(i);
        }
        return ans;
    }
};